1. Field
Various features relate to methods and devices for prime number generation, and more particularly, to methods and devices that accelerate prime number generation.
2. Background
Prime numbers are used widely in public key cryptography. For example, RSA (Rivest, Shamir, Adleman) is one of the most widely used public key ciphers that requires prime numbers for its key generation process. Prime numbers used in cryptography must be large enough to ensure a large key space, which frustrates brute force attacks.
Typical prime numbers that may be used for an RSA cryptography scheme may be, for example, 1,024 bits, which results in a 2,048 bit public/private key pair. At this time, generating prime numbers this large is time consuming even for personal computers and servers having relatively advanced processors and results in noticeable delay. This delay becomes a critical factor that affects mobile computing when RSA key generation is needed for certain applications, e.g., Trusted Platform Module (TPM) and smart cards (UICC). Generating 1,024 bit prime numbers in the latest ARM based processors may take a delay on the order of seconds, which significantly affects the user experience. Thus, any methods that accelerate prime number generation will benefit cryptographic applications, especially in mobile computing applications.
FIG. 1 illustrates a typical method 100 found in the prior art to generate a prime number. First, a random number R of n words is generated using either a true random number generator (RNG) or a high quality pseudo random number generator (PRNG) 102. Second, a “primality test” is executed on the candidate number R 104. A “primality test” is an algorithm for determining whether a number is prime. In many cases, primality tests are actually composite number tests (i.e., they determine whether a number is a composite number) that are probabilistic in nature. Examples of such tests include the Miller-Rabin primality test and Solovay-Strassen primality test.
Third, if the candidate number R passes the primality test (i.e., the number R is probably prime) then R may be used as a prime number in the key generation process 106. Otherwise, if the candidate number R fails the primality test (i.e., the number R is determined not to be prime), then the number R is discarded and a completely new random number R2 is generated 108 and the above steps 104, 106, and/or 108 are repeated.
Although the primality test contributes a majority of the delay associated with prime number generation, another significant contributor of the delay is due to the time spent generating new random numbers R (i.e., step 102) after it is determined that a candidate random number is not prime (i.e., step 108). The probability of a randomly selected number R being prime is very low. For example, according to the prime number theorem the probability that a 1,024-bit number is prime is about is 1 in 710 (1/ln (21024)). For this reason, a candidate prime number may be discarded (i.e., step 108) and a new candidate prime number may be generated (i.e., step 102) numerous times before a candidate prime number is confirmed (to a certain degree) to be prime (i.e., step 106).
Thus, there exists a need to accelerate prime number generation so that the overall delay associated with generating and determining a number to be prime is reduced. Applications related to cryptography that rely on prime number generation may derive significant benefits from such accelerated prime number generation schemes.